In this paper, we study k-means++ and k-means||, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means||. Our results give a better theoretical justification for why these algorithms perform extremely well in practice.

The most popular heuristic for solving this problem is Lloyd's algorithm ( Lloyd,

The metric k -center clustering problem with z outliers, also known as (k,z) -center clustering, involves clustering a given point set P in a metric space (M,d) using at most k balls, minimizing the maximum ball radius while excluding up to z points from the clustering. This problem holds fundamental significance in various domains such as machine learning, data mining, and database systems.This paper addresses the fully dynamic version of the problem, where the point set undergoes continuous updates (insertions and deletions) over time. The objective is to maintain an approximate (k,z) -center clustering with efficient update times. We propose a novel fully dynamic algorithm that maintains a (4 \epsilon) -approximate solution to the (k,z) -center clustering problem that covers all but at most (1 \epsilon)z points at any time in the sequence with probability 1-k/e {\Omega(\log k)} . The algorithm achieves an expected amortized update time of \mathcal{O}(\epsilon {-2} k 6\log(k) \log(\Delta)), and is applicable to general metric spaces.

Summary and Contributions: In this submission new bounds on the approximation factor of k-means and k-means are presented. The first theoretical contribution is an upper bound of 5(ln(k) 2) on the approximation factor of k-means, which improved upon the previously known upper bound of 8(ln(k) 2) by a constant factor. Then bicriteria approximations are considered, i.e., one uses k-means and k-means to compute clusterings with k Delta clusters for some Delta 0 and compares the costs of these clusterings with those of an optimal k-clustering. Both for k-means and k-means such bicriteria results are already known but in this submission improved bounds are shown. These improved bounds exhibit almost the same asymptotic behavior with respect to Delta as the known bounds but the constants are significantly smaller.

Although the improved analysis does not offer a huge jump compared to the known bounds, the importance of this algorithm and the simplification of the proof makes the paper an important contribution. Please give some discussion on how your results are orthogonal to the recent results by Rozhon (we agree that they are orthogonal).

In this paper, we study k-means and k-means, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means and k-means . Our results give a better theoretical justification for why these algorithms perform extremely well in practice.